package com.demo.java.OD301_350.OD338;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找到它(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146155630
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取矩阵大小，输入格式为：行数 列数
        String line = scanner.nextLine().trim();
        int M = Integer.parseInt(line.split(" ")[0]);  // M 表示列数
        int N = Integer.parseInt(line.split(" ")[1]);  // N 表示行数

        // 读取要查找的字符串
        String W = scanner.nextLine().trim();

        // 读取矩阵的每一行，转换为字符数组
        char[][] matrix = new char[N][M];
        for (int i = 0; i < N; i++) {
            String row = scanner.nextLine().trim();
            matrix[i] = row.toCharArray();  // 将每一行字符串转换为字符数组
        }

        // 调用求解方法，返回结果
        String res = solveMethod(matrix, W);
        System.out.println(res);  // 输出结果
    }

    /**
     * 查找方法：用于判断是否从当前位置开始匹配字符串
     * @param board 矩阵
     * @param visited 已访问标记矩阵
     * @param x 当前字符的横坐标
     * @param y 当前字符的纵坐标
     * @param s 需要查找的目标字符串
     * @param k 当前需要匹配的目标字符串的字符索引
     * @return 如果从当前位置能够匹配整个字符串，返回 true；否则返回 false
     */
    private static boolean find(char[][] board, boolean[][] visited, int x, int y,
                                String s, int k) {
        // 如果当前字符不匹配目标字符串的第 k 个字符，返回 false
        if (board[x][y] != s.charAt(k)) {
            return false;
        }
        // 如果已经匹配到字符串的最后一个字符，返回 true
        else if (k == s.length() - 1) {
            return true;
        }

        // 标记当前位置为已访问
        visited[x][y] = true;

        // 定义四个方向的偏移量：右、左、下、上
        int[][] dic = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // 遍历四个方向
        for (int[] dir : dic) {
            int newx = x + dir[0];  // 计算新的横坐标
            int newy = y + dir[1];  // 计算新的纵坐标

            // 如果新坐标合法且未被访问过
            if (newx >= 0 && newx < board.length && newy >= 0 && newy < board[0].length) {
                if (!visited[newx][newy]) {
                    // 递归调用查找方法，继续从新坐标查找下一个字符
                    boolean flag = find(board, visited, newx, newy, s, k + 1);
                    if (flag) {
                        return true;  // 如果找到，返回 true
                    }
                }
            }
        }

        // 如果四个方向都没找到匹配的字符，回溯：将当前位置标记为未访问
        visited[x][y] = false;
        return false;  // 返回 false，表示当前路径不行
    }

    /**
     * 求解方法：遍历矩阵，查找目标字符串
     * @param board 矩阵
     * @param word 目标字符串
     * @return 如果找到匹配的字符串，返回其起始位置（行号 列号），否则返回 "NO"
     */
    private static String solveMethod(char[][] board, String word) {
        int h = board.length;  // 矩阵的行数
        int w = board[0].length;  // 矩阵的列数
        boolean[][] visited = new boolean[h][w];  // 用于标记每个位置是否已访问

        // 遍历矩阵中的每个位置，尝试从该位置开始查找目标字符串
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 调用查找方法，从当前位置 (i, j) 开始查找字符串
                boolean flag = find(board, visited, i, j, word, 0);
                if (flag) {
                    // 如果找到匹配的字符串，返回该字符串的起始坐标，注意行列是从 1 开始的
                    return (i + 1) + " " + (j + 1);
                }
            }
        }

        // 如果遍历完矩阵都没找到匹配的字符串，返回 "NO"
        return "NO";
    }
}
